/* Cache.

   Copyright (C) 2001, 2002, 2003 Stefan Maierhofer.

   Written by Stefan Maierhofer <sm@cg.tuwien.ac.at>

   This file is part of Vecmath.

   Vecmath is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   Vecmath is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with Vecmath; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. */

using System;
using System.Collections;
using NUnit.Framework;

namespace Vecmath.Utils
{
    public class Cache
    {

        public Cache(int capacity)
        {
            this.capacity = capacity;
        }

        public object this [object key]
        {
            get { return Get(key); }
            set { Insert(key, value); }
        }

        public int Size
        {
            get {return size; }
        }

        public bool Contains(object key)
        {
            return hashtable.ContainsKey(key);
        }

        public void Insert(object key, object val)
        {
            // if key exists replace it and return
            if (hashtable.ContainsKey(key))
            {
                ((CacheEntry)hashtable[key]).val = val;
                return;
            }

            // remove lru entry if element count equals capacity
            if (size == capacity) RemoveFromHead();

            CacheEntry e = new CacheEntry(key, val);
            AddToTail(e);
            hashtable[key] = e;
        }

        public object Get(object key)
        {
            if (!hashtable.ContainsKey(key)) return null;
            CacheEntry e = (CacheEntry)hashtable[key];
            MoveToTail(e);
            return e.val;
        }

        protected void RemoveFromHead()
        {
            if (size == 0) return;

            size--;

            hashtable.Remove(head.key);

            if (size == 0)
            {
                head = tail = null;
            }
            else 
            {
                head = head.next;
            }
        }

        protected void AddToTail(CacheEntry e)
        {
            size++;

            if (tail == null)
            {
                head = tail = e;
                e.prev = null;
                e.next = null;
                return;
            }

            tail.next = e;
            e.prev = tail;
            e.next = null;
            tail = e;
        }

        protected void MoveToTail(CacheEntry e)
        {
            // tail element
            if (e == tail) return;

            // head element
            if (e == head)
            {
                head = head.next;
                tail.next = e;
                e.prev = tail;
                e.next = null;
                tail = e;
                return;
            }
            // inner element
            e.prev.next = e.next;
            e.next.prev = e.prev;
            tail.next = e;
            e.prev = tail;
            e.next = null;
            tail = e;
        }

        protected class CacheEntry
        {
            public CacheEntry(object key, object val)
            {
                this.key = key;
                this.val = val;
                prev = next = null;
            }

            public object val;
            public object key;
            public CacheEntry next;
            public CacheEntry prev;
        }

        CacheEntry head = null;
        CacheEntry tail = null;

        protected int capacity;
        protected int size = 0;
        protected Hashtable hashtable = new Hashtable();

    }


    [TestFixture]
    public class CacheTest
    {

        [Test]
        public void CacheCreation()
        {
            Cache c = new Cache(3);
            Assert.IsNotNull(c);
        }

        [Test]
        public void Insertion()
        {
            Cache c = new Cache(3);
            c.Insert(1,1);
            Assert.IsTrue(c.Size == 1);

            c.Insert(2,2);
            c.Insert(3,3);
            Assert.IsTrue(c.Size == 3);
        }

        [Test]
        public void CacheFull()
        {
            Cache c = new Cache(3);
            c.Insert(1,1);
            c.Insert(2,2);
            c.Insert(3,3);
            c.Insert(4,4);
            Assert.IsTrue(c.Size == 3);
        }

        [Test]
        public void Hit()
        {
            string s = "abc";
            Cache c = new Cache(3);
            c[123] = s;
            object o = c[123];
            Assert.AreEqual(s, o);
        }

        [Test]
        public void Miss()
        {
            Cache c = new Cache(3);
            object o = c[123];
            Assert.IsNull(o);
        }

        [Test]
        public void Miss2()
        {
            string s = "abc";
            Cache c = new Cache(3);
            c[123] = s;
            c[1] = 1;
            c[2] = 2;
            c[3] = 3;
            object o = c[123];
            Assert.IsNull(o);
        }

        [Test]
        public void Hit2()
        {
            string s = "abc";
            object o;
            Cache c = new Cache(3);
            c[123] = s;
            c[1] = 1;
            c[2] = 2;
            o = c[123];
            c[3] = 3;
            o = c[123];
            Assert.AreEqual(s, o);
            Assert.AreEqual(2, c[2]);
            Assert.AreEqual(3, c[3]);
            Assert.IsNull(c[1]);
        }

        [Test]
        public void Get()
        {
            string s = "abc";
            Cache c = new Cache(3);
            c[123] = s;
            
            Assert.AreEqual(c[123], c.Get(123));
        }
    }

}
